package OfferLanQiaoBei.a_12届蓝桥真题;

import java.util.Scanner;

/*
你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN
请你计算一共可以称出多少种不同的正整数重量？
注意砝码可以放在天平两边。

输入格式
输入的第一行包含一个整数 N
第二行包含 N 个整数：W1,W2,W3,⋅⋅⋅,WN

输出格式
输出一个整数代表答案

数据范围
对于 50%的评测用例，1≤N≤15。
对于所有评测用例，1≤N≤100，N 个砝码总重不超过 10^5




输入样例：
3
1 4 6

输出样例：
10

样例解释
能称出的 10种重量是：1、2、3、4、5、6、7、9、10、11。




背包问题
	也称有限制的选择问题
这里认为0不算
 */
public class g最少砝码给数量求能称多少数 {
	public static void main(String[] args) {
		g最少砝码给数量求能称多少数 test = new g最少砝码给数量求能称多少数();
		test.useDeal();
	}
	
	public void useDeal() {
		Scanner scanner = new Scanner(System.in);
		int Number = scanner.nextInt();
		int maxWeight = 0;
		int[] weight = new int[Number + 1];
		for (int i = 1; i < Number + 1; i++) {
			weight[i] = scanner.nextInt();
			maxWeight += weight[i];
		}
		boolean[][] flag = new boolean[Number + 1][2 * maxWeight];//列要足够大
		flag[0][0] = true;
		int res = deal(weight, flag, Number, maxWeight);
		System.out.println(res);
	}
	
	/**
	 * 运用了DP思想
	 * 闫式DP
	 * 当前的boolean取决于三种以前的状态
	 * @param weight
	 * @param flag
	 * @param Number
	 * @param maxWeight
	 * @return
	 */
	public int deal(int[] weight, boolean[][] flag, int Number, int maxWeight) {
		for (int i = 1; i < Number + 1; i++) {
			for (int j = 0; j < maxWeight + 1; j++) {
				flag[i][j] = flag[i - 1][j] || flag[i - 1][j + weight[i]] || flag[i - 1][Math.abs(j - weight[i])];
							//什么都不选					选中放右边							选中放右边
							//即前i-1个砝码就足够称出重量j	即前i-1个砝码能称出j+weight[i]重量	即前i-1个砝码能称出j-weight[i]重量
			}
		}
		int res = 0;
		for (int i = 1; i < maxWeight + 1; i++) {
			if (flag[Number][i]) {//对于Number个砝码来说，从1到maxWeight，有多少个重量是true
				res++;
			}
		}
		return res;
	}
}
